package org.example.StacksAndQueues;

import java.util.ArrayDeque;
import java.util.Stack;

public class Remove_all_adjacent_duplicates_in_the_string {
    public static void main(String[] args) {
        //删除字符串中的所有相邻重复项

        //给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
        //在 S 上反复执行重复项删除操作，直到无法继续删除。
        //在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
        String s = "abbaca";
        System.out.println(removeDuplicates2(s));
    }
    public static String removeDuplicates(String s) {
        StringBuilder sb = new StringBuilder(s);
        Stack<Character> stack = new Stack<>();
        int len = sb.length();
        for (int i = 0; i < len; i++) {
            if (!stack.empty() && stack.peek()==sb.charAt(i)){
                stack.pop();
                sb.deleteCharAt(i-1);
                sb.deleteCharAt(i-1);
                len-=2;
                i-=2;
            }else {
                stack.add(sb.charAt(i));
            }
        }
        return sb.toString();
    }
    public static String removeDuplicates2(String S) {
        //ArrayDeque会比LinkedList在除了删除元素这一点外会快一点
        //参考：https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist
        ArrayDeque<Character> deque = new ArrayDeque<>();
        char ch;
        for (int i = 0; i < S.length(); i++) {
            ch = S.charAt(i);
            if (deque.isEmpty() || deque.peek() != ch) {
                deque.push(ch);
            } else {
                deque.pop();
            }
        }
        String str = "";
        //剩余的元素即为不重复的元素
        while (!deque.isEmpty()) {
            str = deque.pop() + str;
        }
        return str;
    }
}
